package com.yc.leetcode;

/**
 * 背包问题
 */
public class PackageProblem {
    public static void main(String[] args) {
        PackageProblem pp = new PackageProblem();
//        pp.m1();
//        pp.m2();
//        pp.m3();
//        pp.m4();
        pp.m5();
    }

    public void m1() {
        int[] weight = {0,6,1,5,2,1};
        int[] value = {0,48,7,40,12,8};
        int n = 5;int w = 8;

        //获得第i个物品，在包容量为j的时候的最大价值（i，j都额外增加了一个0）
        int[][] dp = maxVal(n,w, weight, value);
        System.out.println("maxVal=" + dp[5][8]);

        //逆推物品序号
        int j = w;
        StringBuffer sb = new StringBuffer();
        for (int i = n; i > 0; i--) {
            if (dp[i][j] > dp[i-1][j]) {
                sb.insert(0, i + " ");
                j -= weight[i];
            }
            if (j == 0) {
                break;
            }
        }
        System.out.println(sb);
    }

    public void m2() {
        int[] weight = {0,6,1,5,2,1};
        int[] value = {0,48,7,40,12,8};
        int N = 5;int W = 8;
        int[][] dp = maxVal2(N, W, weight, value);

        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= W; j++) {
                System.out.printf("(%d,%d)=%-5d", i, j, dp[i][j]);
            }
            System.out.println();
        }

        // 背包能够装入物品的最大值为
        int maxValue = dp[N][W];
        System.out.printf("maxValue=%d", maxValue);
        System.out.println();
        // 逆推找出装入背包的所有商品的编号
        int j = W;
        String numStr = "";
        for (int i = N; i > 0; i--) {
            // 若dp[i][j]>dp[i-1][j], 则说明第i件物品放入背包
            if (dp[i][j] > dp[i - 1][j]) {
                numStr = i + " " + numStr;
                j = j - weight[i];
            }
            if (j <= 0) {
                break;
            }
        }

        System.out.printf("goods=%s", numStr);
    }

    public void m3() {
        int[] weight = {6,1,5,2,1};
        int[] value = {48,7,40,12,8};
        int w = 8;
        StringBuffer sb = new StringBuffer();
        System.out.println("maxVal=" + maxVal_uuu(w, weight, value, sb));
        System.out.println("select: " + sb);

    }

    public void m4() {
        int[] weight = {6,1,5,2,1};
        int[] value = {48,7,40,12,8};
        int w = 8;
        System.out.println("maxVal=" + maxVal_most(w, weight, value));

    }

    /**
     * 完全背包问题
     */
    public void m5() {
        int[] weight = {6,1,5,2,1};
        int[] value = {48,7,40,12,8};
        int w = 8;
        System.out.println("maxVal=" + every_maxVal_most(w, weight, value));

    }

    /**
     * 完全背包问题的问题：横轴的重量增加要以物品的最小公约数增加，否可可能出错
     * 因为数据定义时已经限制了物品重量太小的情况。如果没限制，那么完全背包的算法就有问题
     */
    public void m5_1() {
        int[] weight = {6,1,5,2,1};
//        int[] weight = {0.006,0.001,0.005,0.002,0.001};
        int[] value = {48,7,40,12,8};
        int w = 8;
        System.out.println("maxVal=" + every_maxVal_most(w, weight, value));

    }

    /**
     * 由于判断条件的问题，比官方方案多存了一张表dp_w
     * 也是正确的，但空间复杂度高了一倍。判断条件更复杂，时间也更慢些
     * @param w 背包总负重
     * @param weight 物品重量
     * @param value 价值
     * @return
     */
    public int[][] maxVal(int n, int w,  int[] weight, int[] value) {
        //定义dp: 纵轴物品  横轴重量。为了方便计算，都增加一个0
        int[][] dp_v = new int[n+1][w+1];
        int[][] dp_w = new int[n+1][w+1];

        //之所以增加包容量为0，前0个物品。
        //目的就是为了方便初始化（从第一个开始那就得一个一个判断了），也方便计算（如果包容量剩余为0，也可以统一计算，不必再判断）
        //初始化第一列：包容量为0时的最优解
        for (int i = 0; i <= n; i++) {
            dp_v[i][0] = 0;
            dp_w[i][0] = 0;
        }
        //初始化第一行：前0个物品的最优解
        for (int i = 0; i <= w; i++) {
            dp_v[0][i] = 0;
            dp_w[0][i] = 0;
        }

        for (int i = 1; i <= n; i++) {//前i个物品
            for (int j = 1; j <= w; j++) {//包总负重
                if (dp_w[i-1][j] + weight[i] <= j) {//前i-1个物品的最优解 + 第i个物品，一起能装的下
                    dp_v[i][j] = dp_v[i-1][j] + value[i];
                    dp_w[i][j] = dp_w[i-1][j] + weight[i];
                } else {//两者无法一起装
                    //装前i-1个物品的最优解  or  装"第i个物品 + 剩余空间下的最优解"， 两者取大的那个
                    if (weight[i] > j) {
                        dp_v[i][j] = dp_v[i-1][j];
                        dp_w[i][j] = dp_w[i-1][j];
                    } else {
                        if (dp_v[i-1][j] > value[i] + dp_v[i-1][j-weight[i]]) {//只加入A
                            dp_v[i][j] = dp_v[i-1][j];
                            dp_w[i][j] = dp_w[i-1][j];
                        } else {//加入b + dp[剩余]
                            dp_v[i][j] = value[i] + dp_v[i-1][j-weight[i]];
                            dp_w[i][j] = weight[i] + dp_w[i-1][j-weight[i]];
                        }
                    }

                }
            }
        }

        return dp_v;
    }



    /**
     * 官方正确解法
     * @param n
     * @param w
     * @param weight
     * @param value
     * @return
     */
    public int[][] maxVal2(int n, int w,  int[] weight, int[] value) {
        // 定义一个数组dp[i][j]  i表示当前物品的序号, j表示当前书包的重量
        int[][] dp = new int[n + 1][w + 1];
        for (int j = 0; j <= w; j++) {  // 物品不存在时，最大价值肯定是0
            dp[0][j] = 0;
        }
        for (int i = 1; i <= n; i++) {  // 背包重量为0时，最大价值肯定是0
            dp[i][0] = 0;
        }

        for (int i = 1; i <= n; i++) {  // 从第1个物品开始选取
            for (int j = 1; j <= w; j++) {
                if (weight[i] <= j) { // 第i件物品重量 小于等于 当前承载重量，根据价值大小判断是否放入。
                    dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
                } else { // 第i件物品重量大于当前承载重量，则不放入。
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp;
    }

    /**
     * 优化
     * @param w         背包总负重
     * @param weight    物品的重量
     * @param value     物品的价值
     * @param select    选择的物品
     * @return
     */
    public int maxVal_u(int w,  int[] weight, int[] value, StringBuffer select) {
        //定义一个二维数组：两行数据（来回替换着用）
        int[][] dp = new int[2][w+1];
        String[][] dp_s = new String[2][w+1];//用来存物品组合字符串
        int index = 0;//指针。表示当前正在处理第index行

        for (int i = 0; i < w; i++) {
            dp_s[0][i] = "";
            dp_s[1][i] = "";
        }

        for (int i = 0; i < value.length; i++) {
            index ^= 1;
            for (int j = 1; j <= w; j++) {
                if (weight[i] > j) {//当前物品重量超过了j
                    dp[index][j] = dp[index^1][j];
                    dp_s[index][j] = dp_s[index^1][j];
                } else {
                    if (dp[index^1][j] > value[i] + dp[index^1][j-weight[i]]) {
                        dp[index][j] = dp[index^1][j];
                        dp_s[index][j] = dp_s[index^1][j];
                    } else {
                        dp[index][j] = value[i] + dp[index^1][j-weight[i]];
                        dp_s[index][j] = dp_s[index^1][j-weight[i]] + " " + (i+1);
                    }

                }
            }

        }
        select.append(dp_s[index][w]);
        return dp[index][w];
    }

    /**
     * 上面的算法进一步优化：只用一个数组（把上面两层替换的数组再缩小一半：通过倒序遍历w）
     * @param w
     * @param weight
     * @param value
     * @param select
     * @return
     */
    public int maxVal_uu(int w,  int[] weight, int[] value, StringBuffer select) {
        //定义一个数组（一行当两行使用）
        int[] dp = new int[w+1];
        //用来存物品组合字符串
        String[] dp_s = new String[w+1];
        //初始化
        for (int i = 0; i < w; i++) {
            dp_s[i] = "";
        }

        for (int i = 0; i < value.length; i++) {
            for (int j = w; j >= 1; j--) {
                if (weight[i] <= j && dp[j] <= value[i] + dp[j-weight[i]]) {
                    dp[j] = value[i] + dp[j-weight[i]];
                    dp_s[j] = dp_s[j-weight[i]] + " " + (i+1);
                }
            }
        }

        select.append(dp_s[w]);
        return dp[w];
    }

    //再优化
    public int maxVal_uuu(int w,  int[] weight, int[] value, StringBuffer select) {
        //定义一个数组（一行当两行使用）
        int[] dp = new int[w+1];
        //用来存物品组合字符串
        String[] dp_s = new String[w+1];
        //初始化
        for (int i = 0; i < w; i++) {
            dp_s[i] = "";
        }

        for (int i = 0; i < value.length; i++) {
            for (int j = w; j >= weight[i]; j--) {//把条件j >= weight[i]上移到for循环的条件判断里
                if (dp[j] <= value[i] + dp[j-weight[i]]) {
                    dp[j] = value[i] + dp[j-weight[i]];
                    dp_s[j] = dp_s[j-weight[i]] + " " + (i+1);
                }
            }
        }

        select.append(dp_s[w]);
        return dp[w];
    }

    //再优化
    public int maxVal_uuuu(int w,  int[] weight, int[] value, StringBuffer select) {
        //定义一个数组（一行当两行使用）
        int[] dp = new int[w+1];
        //用来存物品组合字符串
        String[] dp_s = new String[w+1];
        //初始化
        for (int i = 0; i < w; i++) {
            dp_s[i] = "";
        }

        for (int i = 0; i < value.length; i++) {
            for (int j = w; j >= weight[i] && dp[j] <= value[i] + dp[j-weight[i]]; j--) {//把条件j >= weight[i]上移到for循环的条件判断里
                dp[j] = value[i] + dp[j-weight[i]];
                dp_s[j] = dp_s[j-weight[i]] + " " + (i+1);
            }
        }

        select.append(dp_s[w]);
        return dp[w];
    }

    /**
     * 最简洁版本（不输出选择的物品）
     * @param w
     * @param weight
     * @param value
     * @return
     */
    public int maxVal_most(int w,  int[] weight, int[] value) {
        //定义一个数组（一行当两行使用）
        int[] dp = new int[w+1];

        for (int i = 0; i < value.length; i++) {
            for (int j = w; j >= weight[i]; j--) {//j < weight[i]没必要计算，因为j包不够大，所以肯定用的还是上一个物品的最优解
                dp[j] = Math.max(dp[j], value[i] + dp[j-weight[i]]);
            }
        }

        return dp[w];
    }

    /**
     * 完全背包问题
     * @param w
     * @param weight
     * @param value
     * @return
     */
    public int every_maxVal_most(int w,  int[] weight, int[] value) {
        //定义一个数组（这里就不是一行当两行使用了，而确实一行当一行）
        int[] dp = new int[w+1];

        for (int i = 0; i < value.length; i++) {
            for (int j = weight[i]; j <= w; j++) {//这里再次变为顺序遍历，是因为每次都是依赖自己（之前算的小包），而不再依赖上一层
                //很巧合的还是这一行代码（但意义完全变了，之前的一行：i行依赖i-1行，只不过i-1行和i行公用一行。现在真的i行依赖i行之前的数据）
                dp[j] = Math.max(dp[j], value[i] + dp[j-weight[i]]);
            }
        }

        return dp[w];
    }

}
